|
In combinatorics, Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let ''r'' and ''s'' be any two positive integers. Ramsey's theorem states that there exists a least positive integer for which every blue-red edge colouring of the complete graph on vertices contains a blue clique on ''r'' vertices or a red clique on ''s'' vertices. (Here signifies an integer that depends on both ''r'' and ''s''.) Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of ''monochromatic subsets'', that is, subsets of connected edges of just one colour. An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, ''c'', and any given integers ''n''1, …, ''nc'', there is a number, ''R''(''n''1, …, ''nc''), such that if the edges of a complete graph of order ''R''(''n''1, ..., ''n''''c'') are coloured with ''c'' different colours, then for some ''i'' between 1 and ''c'', it must contain a complete subgraph of order ''n''''i'' whose edges are all colour ''i''. The special case above has ''c'' = 2 (and ''n''1 = ''r'' and ''n''2 = ''s''). ==Example: ''R''(3, 3) = 6== In the 2-colour case, an arbitrary simple graph ''G'' = (''V'', ''E'') can be identified with the complete graph on the vertex set ''V'' whose edges are coloured with two colours (all the edges corresponding to those in ''E'' receive one colour and all the other edges receive the other colour.) This permits talking about Ramsey's theorem using "connected" and "non-connected" terminology instead of colours, but this language does not generalize to a greater number of colours. In the following example, the formula ''R''(3, 3) provides a solution to the question which asks for the minimum number of vertices a graph must contain in order to ensure that either: # at least 3 vertices in the graph are mutually connected (form a clique), ''or'' # at least 3 vertices in the graph are mutually unconnected (an independent set). The remainder of this article will use the more common colour terminology and refer to monochromatic cliques. Note that owing to the symmetrical nature of the problem space, ''R''(''r'', ''s'') is equal to ''R''(''s'', ''r''). Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex, ''v''. There are 5 edges incident to ''v'' and so (by the pigeonhole principle) at least 3 of them must be the same colour. Without loss of generality we can assume at least 3 of these edges, connecting the vertex, ''v'', to vertices, ''r'', ''s'' and ''t'', are blue. (If not, exchange red and blue in what follows.) If any of the edges, (''r'', ''s''), (''r'', ''t''), (''s'', ''t''), are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have an entirely red triangle. Since this argument works for any colouring, ''any'' ''K''6 contains a monochromatic ''K''3, and therefore ''R''(3, 3) ≤ 6. The popular version of this is called the theorem on friends and strangers. An alternative proof works by double counting. It goes as follows: Count the number of ordered triples of vertices, ''x'', ''y'', ''z'', such that the edge, (''xy''), is red and the edge, (''yz''), is blue. Firstly, any given vertex will be the middle of either 0 × 5 = 0 (all edges from the vertex are the same colour), 1 × 4 = 4 (four are the same colour, one is the other colour), or 2 × 3 = 6 (three are the same colour, two are the other colour) such triples. Therefore, there are at most 6 × 6 = 36 such triples. Secondly, for any non-monochromatic triangle (xyz), there exist precisely two such triples. Therefore, there are at most 18 non-monochromatic triangles. Therefore, at least 2 of the 20 triangles in the ''K''6 are monochromatic. Conversely, it is possible to 2-colour a ''K''5 without creating any monochromatic ''K''3, showing that ''R''(3, 3) > 5. The unique colouring is shown to the right. Thus ''R''(3, 3) = 6. The task of proving that ''R''(3, 3) ≤ 6 was one of the problems of William Lowell Putnam Mathematical Competition in 1953. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ramsey's theorem」の詳細全文を読む スポンサード リンク
|